# LeetCode 130、被围绕的区域
# 一、题目描述
给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
# 二、题目解析
# 三、参考代码
# 1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// https://leetcode.cn/problems/surrounded-regions/
class Solution {
public void solve(char[][] board) {
// 矩阵的行数
int m = board.length;
// 矩阵的列数
int n = board[0].length;
// 利用两个 for 循环，遍历矩阵中的一些特殊的单元格，将它们赋值为 N
// 特殊的单元格：必然是从边界处开始的
for (int i = 0; i < m; i++){
for (int j = 0; j < n; j++){
// i == 0：表示在第 0 行，处于边界位置
// j == 0：表示在第 0 列，处于边界位置
// i == (m - 1)：表示在最后一行，处于边界位置
// j == (n - 1)：表示在最后一列，处于边界位置
if (i == 0 || j == 0 || i == (m - 1) || j == (n - 1)){
// 从这些单元格开始向腹部延伸下去，找到所有和边界单元格想通的那些 O
dfs(board, i, j);
}
}
}
// 第二个 for 循环，开始修改
for (int i = 0; i < m; i++){
for (int j = 0; j < n; j++){
// board[i][j] == 'O' 表示无法从边界格子中延伸过来
// 表示被 'X' 围绕的区域
if (board[i][j] == 'O'){
// 修改为 X
board[i][j] = 'X';
}
// board[i][j] == 'N' 表示是从边界格子中延伸过来
if (board[i][j] == 'N'){
// 修改为 O
board[i][j] = 'O';
}
}
}
}
public void dfs(char[][] board, int i, int j) {
// dfs搜索、递归终止条件
// i < 0 ，越界
// j < 0 ，越界
// i >= board.length ，越界
// j >= board[0].length ，越界
// board[i][j] == X ，不需要继续搜索下去
// board[i][j] == N ，这个格子已经被访问过，不需要继续搜索下去
if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] == 'X' || board[i][j] == 'N') {
return ;
}
// 否则说明当前单元格是 O，最后需要保留下来的那种
// 将当前单元格置为 N ，避免其它格子 dfs 过程中又把它加入到计算中
board[i][j] = 'N';
// 在当前单元格的四个方向开始搜索
// 上：（ 0 ， -1 ）
// 下：（ 0 ， 1 ）
// 左：（ -1 ， 0 ）
// 右：（ 1 ， 0 ）
// dx 为行的方向数组
int dx[] = { -1 , 1 , 0 , 0 };
// dy 为行的方向数组
int dy[] = { 0 , 0 , -1 , 1 };
// 朝着这四个方向开始延伸搜索下去
for (int index = 0; index < 4; index++) {
// 下一个即将去搜索网格的横坐标
int next_i = i + dx[index];
// 下一个即将去搜索网格的纵坐标
int next_j = j + dy[index];
// 继续搜索
dfs(board,next_i,next_j);
}
}
}
# **2、**C++ 代码
class Solution {
public:
void solve(vector<vector<char>>& board) {
// 矩阵的行数
int m = board.size();
// 矩阵的列数
int n = board[0].size();
// 利用两个 for 循环，遍历矩阵中的一些特殊的单元格，将它们赋值为 N
// 特殊的单元格：必然是从边界处开始的
for (int i = 0; i < m; i++){
for (int j = 0; j < n; j++){
// i == 0：表示在第 0 行，处于边界位置
// j == 0：表示在第 0 列，处于边界位置
// i == (m - 1)：表示在最后一行，处于边界位置
// j == (n - 1)：表示在最后一列，处于边界位置
if (i == 0 || j == 0 || i == (m - 1) || j == (n - 1)){
// 从这些单元格开始向腹部延伸下去，找到所有和边界单元格想通的那些 O
dfs(board, i, j);
}
}
}
// 第二个 for 循环，开始修改
for (int i = 0; i < m; i++){
for (int j = 0; j < n; j++){
// board[i][j] == 'O' 表示无法从边界格子中延伸过来
// 表示被 'X' 围绕的区域
if (board[i][j] == 'O'){
// 修改为 X
board[i][j] = 'X';
}
// board[i][j] == 'N' 表示是从边界格子中延伸过来
if (board[i][j] == 'N'){
// 修改为 O
board[i][j] = 'O';
}
}
}
}
public:
void dfs(vector<vector<char>>& board, int i, int j) {
// dfs搜索、递归终止条件
// i < 0 ，越界
// j < 0 ，越界
// i >= board.length ，越界
// j >= board[0].length ，越界
// board[i][j] == X ，不需要继续搜索下去
// board[i][j] == N ，这个格子已经被访问过，不需要继续搜索下去
if (i < 0 || j < 0 || i >= board.size() || j >= board[0].size() || board[i][j] == 'X' || board[i][j] == 'N') {
return ;
}
// 否则说明当前单元格是 O，最后需要保留下来的那种
// 将当前单元格置为 N ，避免其它格子 dfs 过程中又把它加入到计算中
board[i][j] = 'N';
// 在当前单元格的四个方向开始搜索
// 上：（ 0 ， -1 ）
// 下：（ 0 ， 1 ）
// 左：（ -1 ， 0 ）
// 右：（ 1 ， 0 ）
// dx 为行的方向数组
int dx[4] = { -1 , 1 , 0 , 0 };
// dy 为行的方向数组
int dy[4] = { 0 , 0 , -1 , 1 };
// 朝着这四个方向开始延伸搜索下去
for (int index = 0; index < 4; index++) {
// 下一个即将去搜索网格的横坐标
int next_i = i + dx[index];
// 下一个即将去搜索网格的纵坐标
int next_j = j + dy[index];
// 继续搜索
dfs(board,next_i,next_j);
}
}
};
# 3、Python 代码
# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# https://leetcode.cn/problems/surrounded-regions/
class Solution:
def solve(self, board: List[List[str]]) -> None:
# 矩阵的行数
m = len(board)
# 矩阵的列数
n = len(board[0])
# 利用两个 for 循环，遍历矩阵中的一些特殊的单元格，将它们赋值为 N
# 特殊的单元格：必然是从边界处开始的
for i in range(0 , m ) :
for j in range( 0 , n ):
# i == 0：表示在第 0 行，处于边界位置
# j == 0：表示在第 0 列，处于边界位置
# i == (m - 1)：表示在最后一行，处于边界位置
# j == (n - 1)：表示在最后一列，处于边界位置
if i == 0 or j == 0 or i == (m - 1) or j == (n - 1) :
# 从这些单元格开始向腹部延伸下去，找到所有和边界单元格想通的那些 O
self.dfs(board, i, j)
# 第二个 for 循环，开始修改
for i in range(0 , m ) :
for j in range( 0 , n ):
# board[i][j] == 'O' 表示无法从边界格子中延伸过来
# 表示被 'X' 围绕的区域
if board[i][j] == 'O' :
# 修改为 X
board[i][j] = 'X'
# board[i][j] == 'N' 表示是从边界格子中延伸过来
if board[i][j] == 'N' :
# 修改为 O
board[i][j] = 'O'
def dfs(self, board: List[List[str]], i : int , j : int ) -> None:
# dfs搜索、递归终止条件
# i < 0 ，越界
# j < 0 ，越界
# i >= board.length ，越界
# j >= board[0].length ，越界
# board[i][j] == X ，不需要继续搜索下去
# board[i][j] == N ，这个格子已经被访问过，不需要继续搜索下去
if i < 0 or j < 0 or i >= len(board) or j >= len(board[0]) or board[i][j] == 'X' or board[i][j] == 'N' :
return
# 否则说明当前单元格是 O，最后需要保留下来的那种
# 将当前单元格置为 N ，避免其它格子 dfs 过程中又把它加入到计算中
board[i][j] = 'N'
# 在当前单元格的四个方向开始搜索
# 上：（ 0 ， -1 ）
# 下：（ 0 ， 1 ）
# 左：（ -1 ， 0 ）
# 右：（ 1 ， 0 ）
# 朝着这四个方向开始延伸搜索下去
for dx, dy in ((0,1), (1,0), (0,-1), (-1,0)):
# 下一个即将去搜索网格的横坐标
next_i = i + dx
# 下一个即将去搜索网格的纵坐标
next_j = j + dy
# 继续搜索
self.dfs(board,next_i,next_j)
# 四、复杂度分析
时间复杂度：O(n×m)，其中 n 和 m 分别为矩阵的行数和列数。深度优先搜索过程中，每一个点至多只会被标记一次。
空间复杂度：O(n×m)，其中 n 和 m 分别为矩阵的行数和列数。主要为深度优先搜索的栈的开销。